package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.List;

import static algo.Operator.exchangeOperator;
import static algo.Operator.leftShiftOperator;
import static algo.Operator.relocatedOperator;
import static algo.Operator.rightShiftOperator;
import static algo.Operator.twoOptOperator;

public class LocalSearch2 extends HeuristicSearch {


    public LocalSearch2(Problem problem) {
        super(problem);
    }

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search init", initSolution);
        Solution finalSolution = search(initSolution);
        PrinterUtils.printTspResult("local search final", finalSolution);
    }

    private Solution initial() {
        GreedySearch greedySearch = new GreedySearch(problem);
        return greedySearch.search();
    }

    public Solution search(Solution initSolution) {
        Solution solution = relocated(initSolution);
        //PrinterUtils.printTspResult("relocate", solution);
        solution = twoOpt(solution);
        //PrinterUtils.printTspResult("2-opt", solution);
        solution = exchange(solution);
        //PrinterUtils.printTspResult("exchange", solution);
        solution = shift(solution, "right");
        //PrinterUtils.printTspResult("right shift", solution);
        solution = shift(solution, "left");
        //PrinterUtils.printTspResult("left shift", solution);
        return solution;
    }

    //*********************  操作算子全遍历 **************************************/

    private Solution relocated(Solution solution) {
        List<Integer> permutation = solution.getPermutation();
        int bestCost = solution.getCost();
        for (int i = 1; i < permutation.size() - 1; i++) {
            for (int j = i + 1; j < permutation.size(); j++) {
                List<Integer> newPermutation = relocatedOperator(permutation, i, j);
                int cost = calculateFitness(newPermutation);
                if (cost < bestCost) {
                    bestCost = cost;
                    permutation = newPermutation;
                }
            }
        }
        return new Solution(permutation, bestCost);
    }

    private Solution twoOpt(Solution solution) {
        List<Integer> permutation = solution.getPermutation();
        int bestCost = solution.getCost();
        for (int i = 1; i < permutation.size() - 1; i++) {
            for (int j = i + 1; j < permutation.size(); j++) {
                List<Integer> newPermutation = twoOptOperator(permutation, i, j);
                int cost = calculateFitness(newPermutation);
                if (cost < bestCost) {
                    bestCost = cost;
                    permutation = newPermutation;
                }
            }
        }
        return new Solution(permutation, bestCost);
    }

    private Solution exchange(Solution solution) {
        List<Integer> permutation = solution.getPermutation();
        int bestCost = solution.getCost();
        for (int i = 1; i < permutation.size() - 1; i++) {
            for (int j = i + 1; j < permutation.size(); j++) {
                List<Integer> newPermutation = exchangeOperator(permutation, i, j);
                int cost = calculateFitness(newPermutation);
                if (cost < bestCost) {
                    bestCost = cost;
                    permutation = newPermutation;
                }
            }
        }
        return new Solution(permutation, bestCost);
    }

    private Solution shift(Solution solution, String direction) {
        List<Integer> permutation = solution.getPermutation();
        int bestCost = solution.getCost();
        for (int i = 1; i < permutation.size() - 1; i++) {
            for (int j = i + 1; j < permutation.size(); j++) {
                int cnt = 1;
                while (cnt++ < (j - i)) {
                    List<Integer> newPermutation =
                            "right".equals(direction)
                                    ? rightShiftOperator(permutation, i, j, 1)
                                    : leftShiftOperator(permutation, i, j, 1);
                    int cost = calculateFitness(newPermutation);
                    if (cost < bestCost) {
                        bestCost = cost;
                        permutation = newPermutation;
                    }
                }
            }
        }
        return new Solution(permutation, bestCost);
    }


}
